Image information, be it color or black and white, is commonly generated in a bitmap format where the bitmap comprises a plurality of gray level pixels, i.e. pixels that are defined by digital values, each value representing a gray level among a number of gray levels. Thus, in an 8 bit system, 256 levels of gray or 256 colors are present, where each level represents an increment of gray between black and white. In the case of color bitmaps, where three defining colors or separations each include 256 levels of information, there may be more than 16 million colors defined by a gray bitmap.
Usually, bitmaps in such a gray level format are unprintable by standard printers. Standard printers print in a limited number of levels, either a spot or a no spot in the binary case, or a limited number of levels associated with the spot, for example, four in the quaternary case. Accordingly, it is necessary to reduce gray level image data to a limited number of levels so that it is printable. Besides gray level information derived by scanning, certain processing techniques such as those described, for example, in U.S. patent application Ser. No. 07/600,542, entitled, "Method for Making Image Conversions With Error Diffusion" by R. Eschbach, produce gray level pixel values which require conversion to a limited set of "legal" or output values.
In high addressability or pulse width modulation printing systems, in contrast to high resolution systems, fine spatial addressing is used in at least one direction (usually the cross process or fast scan direction) while still using a relatively coarse spot. Thus, a high resolution system might operate at 600.times.600 spi, with a spot that is 1/600.times.1/600 square inches. In contrast, a high addressability system might operate at 400.times.1600 spi, with a spot that is 1/400.times.1/400 square inches. Such a high addressability system can produce a spot or mark that is 1/400.times.1/400, 1/400.times.5/1600, 1/400.times.6/1600, 1/400.times.7/1600, etc. Such an arrangement is an improvement over a standard printer, which prints at 1/400.times.1/400, 1/400.times.2/400, 1/400.times.3/400, 1/400.times.4/400.
A process commonly referred to as error diffusion, which converts gray images to binary or other number of level images while attempting to preserve local optical density exist is taught, for example, in "An Adaptive Algorithm for Spatial Greyscale" by Floyd and Steinberg, Proceedings of the SID 17/2, 75-77(1976) (hereinafter, "Floyd and Steinberg"). Another, more elaborate method is taught in U.S. Pat. No. 5,045,952 to Eschbach, assigned to the same assignee as the present invention, which provides image dependent edge enhancement in an error diffusion process. Additional modifications to the error diffusion algorithm as taught by Floyd and Steinberg have been proposed, e.g.: a different weighting matrix, as taught, for example, in "A Survey of Techniques for the Display of Continuous Tone Pictures on Bilevel Displays" by Jarvis et., Computer Graphics and Image Processing, Vol. 5., pp.13-40 (1976), and in "MECCA - A Multiple-Error Correction Computation Algorithm for Bi-Level Image Hardcopy Reproduction" by Stucki, IBM Res. Rep. RZ1060 (1981). Modifications of the error calculation and weight allocation have been taught, for example, in U.S. Pat. No. 4,924,322 to Kurosawa et. al., U.S. Pat. No. 4,339,774 to Temple, and U.S. Pat. No. 4,955,065, to Ulichney. Other error diffusion methods include U.S. patent application Ser. No. 07/600,542, entitled "Method of Making Image Conversions with Error Diffusion" to Eschbach; Ser. No. 07/672,987, entitled "Method of Error Diffusion with Application of Multiple Error Diffusion Matrices" by Eschbach; Ser. No. 07/755,380, entitled "Method for Quantization of Gray Level Pixel Data with Application of Under Compensated Error Diffusion", by Eschbach et al., all assigned to the same assignee as the present invention. Another modification to the method of error diffusion was taught by Billotet-Hoffmann and Bryngdahl, Proceedings of the SID, Vol. 24/3, (1983), pp. 253-258 (hereinafter, Billotet-Hoffmann and Bryngdahl). A dither matrix is used as a repeating set of thresholds for error diffusion, to alleviate the problems of undesired patterns generally produced by the error diffusion algorithm. A distinct method using a dither matrix of large dynamic range together with an edge enhanced error diffusion algorithm is taught in U.S. patent application Ser. No. 07/800,811, entitled "Halftoning with Enhanced Dynamic Range and Edge Enhanced Error Diffusion" by Eschbach.
Error diffusion attempts to maintain gray by making the conversion from gray image signals to binary or other level image signals on a pixel-by-pixel basis. The procedure examines each image signal with respect to a threshold or set of thresholds, and a difference signal, representing the difference in optical density between the modified input image signal and output image signal is forwarded and added to a selected group or set of neighboring pixels, in accordance with a predetermined weighting scheme.
A problem noted with the use of the standard error diffusion algorithms for printing applications is the production of large numbers of isolated black and/or white pixels which are non-printable by many types of printers. The problem remains in high addressability printing. However, in high addressability printing, a large number of high addressability pixels in a scan line make up a spot the size of a single pixel in standard printing. Additionally, while the data may represent, for example, a small group of pixels interspersed with black and white high addressability pixels, the distinction will not be printed due to the overlapping nature of the high addressability pixels. Thus, information may become lost.
A method to overcome the printability problem of standard printing (non-high addressability printing) is taught by U.S. Pat. No. 4,654,721 to Goertzel, where a method is shown to convert a continuous tone image to a bilevel pixel image. The total error generated in one halftone cell is distributed to a predetermined number of adjacent halftone cells. In this way, printable images are generated, while the banding artifact is reduced, by alternating between fixed output dot patterns. Because of an inherent lack of partial dots in this process, evidenced as a loss in sharpness, edge detection and sharpening was included. See, also, "Digital Halftoning in the IBM 4250 Printer" by Goertzel et al. (Goertzel), IBM J. Res. Develop., Vol. 31, No. 1, January 1987. U.S. patent application Ser. No. 07/583,337 by Shiau, and Ser. No. 07/775,201 to Fan, teach the use of similar methods to reduce a continuous tone image to a multilevel pixel image with diffusion of error between adjacent cells. These methods are believed inadequate for high addressability printing.